﻿#include "Trie.h"
#include <cstring>

Trie::Trie()
{
    root = new TrieNode();
}

void Trie::insert(const char* word)
{
    const char* characters = word;
    TrieNode* node = root;
    node->pass++;

    const size_t characterSize = strlen(word);
    for (int i = 0; i < characterSize; i++) {
        const char character = characters[i];
        const int index = character - 'a';
        if (!node->nexts[index]) {
            node->nexts[index] = new TrieNode();
        }

        node = node->nexts[index];
        node->pass++;
    }

    node->end++;
}

int Trie::search(const char* word) const
{
    const char* characters = word;
    const TrieNode* node = root;
    const size_t characterSize = strlen(word);
    for (int i = 0; i < characterSize; i++) {
        const char character = characters[i];
        const int index = character - 'a';
        if (!node->nexts[index]) {
            return 0;
        }

        node = node->nexts[index];
    }

    return node->end;   
}

void Trie::del(const char* word)
{
    if (search(word) == 0) return;

    const char* characters = word;
    TrieNode* node = root;
    const size_t characterSize = strlen(word);

    for (int i = 0; i < characterSize; i++) {
        const char character = characters[i];
        const int index = character - 'a';
        --node->nexts[index]->pass;
        if (node->nexts[index]->pass == 0) {
            delete(node->nexts[index]);
            node->nexts[index] = nullptr;
            return;
        }

        node = node->nexts[index];
    }

    node->end--;
}

int Trie::prefixNumber(const char* preStr)
{
    if (!preStr) return 0;

    const char* characters = preStr;
    TrieNode* node = root;
    const size_t characterSize = strlen(preStr);

    for (int i = 0; i < characterSize; i++) {
        const char character = characters[i];
        const int index = character - 'a';
        if (!node->nexts[index]) return 0;

        node = node->nexts[index];
    }

    return node->pass;
}
